package mo.daliy;

import java.util.HashMap;
import java.util.Map;

public class L3177 {

    public int maximumLength(int[] nums, int k) {
        int[][] dp = new int[nums.length][k+1];
        int[] dptBefore = new int[k+1];
        Map<Integer, Integer>[] dpt = new HashMap[k+1];
        for (int i = 0; i < dpt.length; i++) {
            dpt[i] = new HashMap<>();
        }
        int ret = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int t = 0; t <= k; t++) {
                int ans = 1;
                if (dpt[t] != null && dpt[t].get(nums[i]) != null) {
                    ans = Math.max(ans, dpt[t].get(nums[i])+1);
                }
                if (t > 0) {
                    ans = Math.max(ans, dptBefore[t-1]+1);
                }
                dp[i][t] = ans;
                ret = Math.max(ans, ret);
            }

            for (int t = 0; t <= k; t++) {
                dptBefore[t] = Math.max(dptBefore[t], dp[i][t]);
                dpt[t].put(nums[i], dp[i][t]);
            }
        }
        return ret;
    }

}
